#include "InnerNode.h"


InnerNode::InnerNode(BufferFrame& page, NodeContext& nodeContext) : page(page), context(nodeContext), header(*(NodeHeader*)(page.getData()))
{
}

InnerNode InnerNode::fromNew(BufferFrame& page, NodeContext& nodeContext)
{
    // An dieser Stelle muss sofort die Page mit einem Initial-Header beschrieben werden, dieser wird im Konstruktor nämlich ausgelesen.
    NodeHeader& header = *(NodeHeader*)(page.getData());
    header.isLeaf = false;
    header.hasNext = false; // TODO: Muss irgendwo noch gesetzt werden
    header.entryCount = 0;
    return InnerNode(page, nodeContext);
}

InnerNode InnerNode::fromExisting(BufferFrame& page, NodeContext& nodeContext)
{
    return InnerNode(page, nodeContext);
}


bool InnerNode::hasEnoughSpaceForNewChild()
{
    //TODO - Dummyimplementation
    return false;
}


/**
 * Nach Ausführung dieser Funktion sind alle Locks aller beteiligten Knoten wieder aufgehoben.
 */
SplitOp InnerNode::insert(char* key, TID tid)
{
    // Richtigen Kindknoten ermitteln
    NodeHeader& header = *((NodeHeader*)(page.getData()));

    // Zeigt auf den ersten Key
    char* currentPosition = (char*)page.getData() + sizeof(NodeHeader) + sizeof(unsigned);

    // Achtung: Es gibt einen Slot mehr als Keys
    unsigned slotIndex = 0;

	for(unsigned i = 0; i < header.entryCount; i++)
	{
	    //currentKey > key  goLeft
		if(context.compare(GREATER, currentPosition, key)) break;

        slotIndex += 1;
		currentPosition += context.keyLen + sizeof(unsigned);
	}

    // Ab dieser Stelle zeigt currentPosition auf den key rechts von dem Verweis, der gegangen werden muss (kann eventuell nicht vorhanden sein, wenn der Slot der letzte war)

	unsigned* childId = (unsigned*)(currentPosition - sizeof(unsigned));

    Node child(*childId, context);
    SplitOp so = child.insertExt(key, tid);

    // der Unterknoten musste aufgesplittet werden
    if (so.splitPerformed) {
        // Hat der Link zum zweiten Knoten in diesem Knoten noch Platz?
        if (header.entryCount < this->getMaxEntryCount()) {
            // Daten an sortierter Stelle einfügen

            // Dahinter liegendes nach rechts verschieben
            for (unsigned i=header.entryCount-slotIndex; i>0; i--) {
                char* copyFrom = currentPosition + ((i-1) * (context.keyLen + sizeof(unsigned)));
                char* copyTo = copyFrom + context.keyLen + sizeof(unsigned);
                memcpy(copyTo, copyFrom, context.keyLen + sizeof(unsigned));
            }

            // Neue Verwzweigung mit aufnehmen
            memcpy(currentPosition, so.key, context.keyLen);
            *((unsigned*)(currentPosition + context.keyLen)) = so.newPageId;

            header.entryCount += 1;
            so.splitPerformed = false;
            free(so.key);
        }
        else {
            // Dieser Knoten muss ebenfalls gesplittet werden

            vector<unsigned> res = context.segment.requestPages(1,1);
            unsigned newInnerNodeId = res[0];

            BufferFrame& newInnerNodePage = context.segment.getPage(newInnerNodeId, true);
            // header erzeugen
            InnerNode newInnerNode = InnerNode::fromNew(newInnerNodePage, context);


            // Daten temporär im Speicher ablegen, und den neuen Eintrag entsprechend einsortieren
            char* overfullPageCopy = (char*)malloc(sizeof(unsigned) + ((header.entryCount + 1) * (context.keyLen + sizeof(unsigned))));

            // Daten VOR dem neuen Element kopieren
            unsigned len = sizeof(unsigned) + (slotIndex * (context.keyLen + sizeof(unsigned)));
            memcpy(overfullPageCopy, ((char*)(this->page.getData())) + sizeof(NodeHeader), len);

            // Neues Element kopieren
            memcpy(overfullPageCopy + len, so.key, context.keyLen);
            // Neue PageID speichern
            *((unsigned*)(overfullPageCopy + len + context.keyLen)) = so.newPageId;

            // Daten NACH dem neuen Element kopieren
            unsigned len2 = (header.entryCount - slotIndex) * (context.keyLen + sizeof(unsigned));
            if (len2>0) memcpy(overfullPageCopy + len + context.keyLen + sizeof(unsigned), ((char*)(this->page.getData())) + sizeof(NodeHeader) + len, len2);

            // Jetzt liegt an overfullPageCopy der gesamte fertige Knoten, aber der passt nicht auf eine Seite.


            //// TEST: Ausgabe des temporären Knotens
            //cout << endl << "*" << *((unsigned*)(overfullPageCopy));
            //for (unsigned i=0; i<header.entryCount; i++) {
            //    char* pos = overfullPageCopy+sizeof(unsigned)+(i*(context.keyLen+sizeof(unsigned)));
            //    cout << " | ";
            //    for (unsigned j=0; j<context.keyLen; j++) cout << *((unsigned*)(pos + j));
            //    cout << "| *" << *((unsigned*)(pos+context.keyLen));
            //}
            //cout << endl;

            // Daten rüberkopieren
            unsigned entriesForLeftNode = (header.entryCount+1) / 2;

            // Linker Knoten
            unsigned leftLen = sizeof(unsigned) + (entriesForLeftNode * (context.keyLen + sizeof(unsigned)));
            memcpy(((char*)(this->page.getData())) + sizeof(NodeHeader), overfullPageCopy, leftLen);

            // Als SplitKey wird der (entriesForLeftNode + 1) Key genommen.
            memcpy(so.key, overfullPageCopy + leftLen, context.keyLen);

            // Rechter Knoten
            unsigned rightLen = sizeof(unsigned) + ((header.entryCount - entriesForLeftNode) * (context.keyLen + sizeof(unsigned)));
            memcpy(((char*)(newInnerNodePage.getData())) + sizeof(NodeHeader), overfullPageCopy + leftLen + context.keyLen, rightLen);

            free(overfullPageCopy);

            NodeHeader& newInnerNodeHeader = *((NodeHeader*)(newInnerNodePage.getData()));

            newInnerNodeHeader.entryCount = header.entryCount - entriesForLeftNode;

            newInnerNodeHeader.hasNext = header.hasNext;
            newInnerNodeHeader.nextPageId = header.nextPageId;
            header.entryCount = entriesForLeftNode;
            header.hasNext = true;
            header.nextPageId = newInnerNodeId;

            so.splitPerformed = true;
            so.newPageId = newInnerNodeId;

            context.segment.unfixPage(newInnerNodePage, true);
        }

        context.segment.unfixPage(page, true);
    }
    else {
        context.segment.unfixPage(page, false);
    }

    return so;
}

TID InnerNode::lookup(char* key)
{
	char* currentPosition = (char*)page.getData() + sizeof(NodeHeader) + sizeof(unsigned);

	for(unsigned i = 0; i < header.entryCount; i++)
	{
		if(context.compare(GREATER, currentPosition, key))
		{	//currentKey > key  goLeft
			unsigned* childId = (unsigned*)(currentPosition - sizeof(unsigned));
			Node child(*childId, context);
			return child.lookup(key);
		}
		else if(i + 1 == header.entryCount)
		{	//letzte Stelle -> goRight
			unsigned* childId = (unsigned*)(currentPosition + context.keyLen);
			Node child(*childId, context);
			return child.lookup(key);
		}
		currentPosition += context.keyLen + sizeof(unsigned);
	}

    return TID(); //shall never happen...hopefully
}

index_iterator InnerNode::lookupRange(char* lower, char* upper)
{
    char* currentPosition = dataStart() + sizeof(unsigned);
    bool foundOne = false;
    unsigned candidate;

    //Suche Kind das Bedingung erfüllt und steige ab - bei mehr als einem behalte das Lock und steige beim ersten ab
    for(unsigned i = 0; i < header.entryCount; i++)
    {
        //cout << "key-node: " << *(unsigned*)currentPosition << endl;
        if(i == 0 && context.compare(GREATER, currentPosition, lower))
        {   //Gehe links runter
            candidate = *(unsigned*)(currentPosition - sizeof(unsigned));
            foundOne = true;
            break;
        }

        if (context.compare(GREATER, currentPosition, lower))
        {   //Gehe links runter
            candidate = *(unsigned*)(currentPosition - sizeof(unsigned));
            foundOne = true;
            break;
        }

        if(i + 1 == header.entryCount && context.compare(SMALLEROREQUAL, currentPosition, upper))
        {   //Gehe rechts runter
            candidate = *(unsigned*)(currentPosition + context.keyLen);
            foundOne = true;
            break;
        }

        currentPosition += context.keyLen + sizeof(unsigned);
    }

    if(!foundOne)
    {   //Nix gefunden
        return index_iterator();
    }

    index_iterator iter;
    Node child(candidate, context);
    iter.add(std::move(child.lookupRange(lower, upper)));
    return iter;
}

RemovalResult* InnerNode::remove(char* key, bool isRoot)
{   //Finde Element
    char* currentPosition = dataStart() + sizeof(unsigned);
    RemovalResult* remResult = NULL;
    bool left;
    int position = -1;

    bla* debug = (bla*)page.getData();

	for(unsigned i = 0; i < header.entryCount; i++)
	{
		if(context.compare(GREATER, currentPosition, key))
		{	//currentKey > key  goLeft
			unsigned* childId = (unsigned*)(currentPosition - sizeof(unsigned));
			Node child(*childId, context);
			remResult = child.remove(key, false);
//			if(remResult->redirectNext && !remResult->wasNode)
//                remResult->newNext = *(unsigned*)(currentPosition + context.keyLen);
			position = i;
			left = true;
			break;
		}
		else if(i + 1 == header.entryCount)
		{	//letzte Stelle -> goRight
			unsigned* childId = (unsigned*)(currentPosition + context.keyLen);
			Node child(*childId, context);
			remResult = child.remove(key, false);
//             if(remResult->redirectNext && !remResult->wasNode)
//                remResult->newNext = *(unsigned*)(currentPosition + context.keyLen);
			position = i;
			left = false;
			break;
		}
		currentPosition += context.keyLen + sizeof(unsigned);
	}

	//Nachbereitung
	if(!remResult || !remResult->removed)
	{   //Element wurde nicht gelöscht
	    if(!remResult)
            remResult = new RemovalResult();
        remResult->wasNode = true;
        return remResult;
	}

    if(remResult->redirectNext)// && remResult->nowEmpty)
	{   //Next Pointer umlegen
	    if(position == 0 && left){} //Kann hier noch nicht umlegen
	    else
	    {
	        char* pos;
	        if(position + 1 == (int)header.entryCount && !left)
	        {   //BUG
	            pos = dataStart() + (position) * (context.keyLen + sizeof(unsigned));
	        }
	        else
	        {
                pos = dataStart() + (position - 1) * (context.keyLen + sizeof(unsigned));
	        }
            unsigned fromChild = *(unsigned*)pos;
            unsigned toChild = remResult->newNext;
            Node child(fromChild, context);
            child.redirectNext(toChild, remResult->lastOneDeleted);
            remResult->redirectNext = false;
	    }
	}

	if(remResult->nowEmpty && header.entryCount == 1 && isRoot)
	{   //In diesem Fall hatte der Root 2 Kinder von denen einer leer geworden ist, jetzt wird der Inhalt des anderen Kindes in den RootNode kopiert
        unsigned keepId = (left)?(*(unsigned*)(dataStart() + sizeof(unsigned) + context.keyLen)):(*(unsigned*)(dataStart()));
        swapNode(left, remResult->keepChildId, keepId);
        return remResult;
	}
	else if(remResult->nowEmpty)
	{
	    if(!remResult->wasNode)
	    {   //Kind was Leaf und ist leer und kann entsorgt werden
            //Kopiere zu behaltende Daten hinter dem Eintrag
            if(position + 1 == (int)header.entryCount && !left)
            {   //Der letzte Eintrag kriegt eine Extrawurst
                remResult->newKey = false;
            }
            else
            {   //Standardfall
                unsigned tmpSize = (header.entryCount - position - 1) * (sizeof(unsigned) + context.keyLen) + sizeof(unsigned);
                char* tmpData = new char[tmpSize];
                char* pagePointer = dataStart() + (position + 1) * (sizeof(unsigned) + context.keyLen);
                memcpy(tmpData, pagePointer, tmpSize);

                //Kopiere Daten zurück und überschreibe dabei den alten Eintrag
                pagePointer -= (sizeof(unsigned) + context.keyLen);
                memcpy(pagePointer, tmpData, tmpSize);
                delete[] tmpData;
            }
            header.entryCount--;
            remResult->nowEmpty = (header.entryCount == 0);
	    }
	    else
	    {   //Kind war InnerNode und jetzt hat man den Stress... ^^
	        char* leftSplit = dataStart() + (position) * (sizeof(unsigned) + context.keyLen);
	        char* keySplit = leftSplit + sizeof(unsigned);
            char* rightSplit = keySplit + context.keyLen;
	        SplitMergeResult* splitRes = mergeSplit(leftSplit, rightSplit, keySplit);

	        if(splitRes->splitted)
	        {   //Key aktualisieren
	            memcpy(leftSplit + sizeof(unsigned), splitRes->newKey, context.keyLen);
	            remResult->nowEmpty = false;
	        }
	        else
	        {   //Eintrag löschen
                if(!(position + 1 == (int)header.entryCount && !left))
                {
                    //Achtung Länge könnte Mist sein
                    int length = pageSize - (rightSplit + sizeof(unsigned) + context.keyLen - (char*)page.getData());
                    cout << "länge: " << length << endl;
                    char* tmpData = new char[length];
                    memcpy(tmpData, rightSplit + sizeof(unsigned) + context.keyLen, length);
                    memcpy(rightSplit, tmpData, length);
                    memcpy(keySplit, splitRes->newKey, context.keyLen);
                    delete[] tmpData;
                }
	            header.entryCount--;
	            remResult->nowEmpty = (header.entryCount == 0);
	        }
	        //delete remResult->newKey;
	        remResult->newKey = NULL; //DEBUG
            delete splitRes;
	    }
	}

    if(remResult->nowEmpty)
    {   //Bin ich jetzt leer? - wenn ja welcher Teil soll behalten werden?
//        remResult->keepChildId = (left)?(*(unsigned*)dataStart()):(*(unsigned*)(dataStart() + sizeof(unsigned) + context.keyLen));
        remResult->keepChildId = (left)?(*(unsigned*)dataStart()):(*(unsigned*)(dataStart()));
    }
    remResult->wasNode = true;


	if(remResult->newKey && !(position == 0 && left))
	{   //Der Key muss angepasst werden
	    remResult->newKey = getNewKey(position);
	    char* pagePointer;
		if(position + 1 == (int)header.entryCount && !left)
		{	//Mal wieder ein Sonderfall wenn im rechtesten Child ein Key verändert wurde   BUG
			pagePointer = dataStart() + sizeof(unsigned) + (position) * (sizeof(unsigned) + context.keyLen);
		}
		else
		{	//Der Key wurde im NICHT rechtesten Child verändert
			pagePointer = dataStart() + sizeof(unsigned) + (position - 1) * (sizeof(unsigned) + context.keyLen);
		}
        memcpy(pagePointer, remResult->newKey, context.keyLen);
        //Wurde grade der kleinste Key verändert? -> Key anpassen
        remResult->newKey = (position == 0 && left)?(dataStart() + sizeof(unsigned)):NULL;
        return remResult;
	}

	remResult->removed = true;
	return remResult;
}

char* InnerNode::dataStart()
{
    return (char*)page.getData() + sizeof(NodeHeader);
}

char* InnerNode::getNewKey(int position)
{
    unsigned* childId = (unsigned*)(dataStart() + (position + 1) * (sizeof(unsigned) + context.keyLen));

    Node child(*childId, context);
    return child.getLeftKey();
}



void InnerNode::swapNode(bool left, unsigned keepChildId, unsigned keepId)
{
    BufferFrame& keepPage = context.segment.getPage(keepId, false);
    NodeHeader* childHeader = (NodeHeader*)keepPage.getData();
    NodeHeader* myHeader = (NodeHeader*)page.getData();

    if(childHeader->isLeaf)
    {
        memcpy((char*)page.getData(), (char*)keepPage.getData(), pageSize);
    }
    else
    {
        if(left)
        {   //Aus dem linken Knoten wird ein Eintrag behalten und der gesamte rechte Knoten
            *(unsigned*)dataStart() = keepChildId;
            unsigned length = pageSize - sizeof(NodeHeader) - context.keyLen - sizeof(unsigned);
            memcpy(dataStart() + sizeof(unsigned) + context.keyLen, (char*)keepPage.getData() + sizeof(NodeHeader), length); //Hier wird der gesamte Inhalt kopiert
            myHeader->entryCount = childHeader->entryCount;
        }
        else
        {
            unsigned length = sizeof(NodeHeader) + (childHeader->entryCount * (sizeof(unsigned) + context.keyLen)) + sizeof(unsigned);
            memcpy((char*)page.getData() + length, dataStart() + sizeof(unsigned), context.keyLen); //Kopiere hier den Key der behalten werden soll
            memcpy(((char*)page.getData() + length + context.keyLen), &keepChildId, sizeof(unsigned)); //Behalte hier den Verweis auf ein Kind
            memcpy((char*)page.getData(), (char*)keepPage.getData(), length); //Kopiere hier den Rest
        }
        myHeader->entryCount++;
    }
    context.segment.unfixPage(keepPage,false);
    //TODO: Hier seite dem Segment zurückgeben
}

/**
*   Mergt zwei InnerNode die Kinder dieses Nodes sind zusammen und splittet sie wieder auf wenn das nötig sein sollte.
    left und right müssen Pointer auf zwei Benachbarte Kinder sein, wobei left links von right steht.
    Die Daten stehen am Ende alle in left oder in beiden Nodes verteilt.
*/
SplitMergeResult* InnerNode::mergeSplit(char* left, char* right, char* key)
{
    unsigned leftId = *(unsigned*)left;
    unsigned rightId = *(unsigned*)right;

    BufferFrame& leftPage = context.segment.getPage(leftId, true);
    BufferFrame& rightPage = context.segment.getPage(rightId, true);

    NodeHeader* leftHeader = (NodeHeader*)leftPage.getData();
    NodeHeader* rightHeader = (NodeHeader*)rightPage.getData();

    const unsigned bothCount = leftHeader->entryCount + rightHeader->entryCount + 1;
    const unsigned twoSize = context.keyLen + sizeof(unsigned);
    const unsigned leftSize = (leftHeader->entryCount * twoSize) + sizeof(unsigned);
    const unsigned rightSize = (rightHeader->entryCount * twoSize) + sizeof(unsigned) + twoSize;
    const unsigned tmpSize = leftSize + rightSize+ context.keyLen;
    char tmpData[tmpSize];

    memcpy(tmpData, (char*)leftPage.getData() + sizeof(NodeHeader), leftSize);                                //Kopiere Inhalt aus linkem Knoten
    memcpy(tmpData + leftSize, key, context.keyLen);                                                          //Kopiere Key zwischen den Knoten
    memcpy(tmpData + leftSize + context.keyLen, (char*)rightPage.getData() + sizeof(NodeHeader), rightSize);  //Kopiere INhalt aus rechtem Knoten

    if(bothCount <= getMaxEntryCount())
    {   //Passt alles in einen Knoten - kein SPlit nötig
        char* newKey = new char[context.keyLen];
        memcpy(newKey, key, context.keyLen);//(char*)leftPage.getData() + sizeof(NodeHeader) + sizeof(unsigned), context.keyLen);

        char leftTmp[pageSize] = {0};
        memcpy(leftTmp, (char*)leftPage.getData(), sizeof(NodeHeader));
        memcpy(leftTmp + sizeof(NodeHeader), tmpData, tmpSize);
        memcpy((char*)leftPage.getData(), leftTmp, pageSize);

        SplitMergeResult* result = new SplitMergeResult();
        result->splitted = false;
        result->newKey = newKey;
        leftHeader->entryCount = bothCount;
        context.segment.unfixPage(leftPage, true);
        context.segment.unfixPage(rightPage, true);
        //Hier rechte Seite wieder zurückgeben
        return result;
    }

    const unsigned leftCount = bothCount / 2;
    const unsigned rightCount = bothCount - leftCount;
    char* newKey = new char[context.keyLen];

    memcpy((char*)leftPage.getData() + sizeof(NodeHeader), tmpData, leftCount * twoSize + sizeof(unsigned));        //Kopiere neuen Inhalt in linken Knoten
    memcpy(newKey, tmpData + leftCount * twoSize + sizeof(unsigned), context.keyLen);                               //Kopiere Key
    memcpy((char*)rightPage.getData() + sizeof(NodeHeader), tmpData + tmpSize - (rightCount * twoSize + sizeof(unsigned)), rightCount * twoSize + sizeof(unsigned));   //Kopiere neuen Inhalt in rechten Knoten

    leftHeader->entryCount = leftCount;
    rightHeader->entryCount = (rightCount - 1);

    SplitMergeResult* result = new SplitMergeResult();
    result->splitted = true;
    result->newKey = newKey;

    context.segment.unfixPage(leftPage, true);
    context.segment.unfixPage(rightPage, true);
    return result;
}

void InnerNode::visualize(IndexVisualizer& vis, unsigned pageId)
{
    string nodeDes = "node" + std::move(IndexVisualizer::toString(pageId)) + " [shape=record, label=\"<id> " + IndexVisualizer::toString(pageId) + " | <count> " + std::move(IndexVisualizer::toString(header.entryCount)) + " | <isLeaf> false | ";
    char* currentPosition = (char*)page.getData() + sizeof(NodeHeader);

    const unsigned maxCount = getMaxEntryCount();

    for(unsigned i = 0; i < maxCount; i++)
    {
        //Alle Einträge durchgehen
        string keyDes = "<key" + std::move(IndexVisualizer::toString(i)) + "> ";
        string keyVal = "";
        string ptrDes = "<ptr" + std::move(IndexVisualizer::toString(i + 1)) + "> ";
        string ptrVal = "";
   //     cout << "i: " << i << endl;
        if(i < header.entryCount)
        {
            if(i == 0)
            {
                //Vor dem ersten Key steht schon ein Verweis auf ein Kind
                nodeDes += "<ptr" + std::move(IndexVisualizer::toString(i)) + "> * | ";
                unsigned* childId = (unsigned*)currentPosition;
                vis.addChildRelation(pageId, 0, *childId);
                Node child(*childId, context);
                child.visualize(vis);
                currentPosition += sizeof(unsigned);
            }
            char* key = currentPosition;
            keyVal = vis.keyToString(key);
            ptrVal = "*";

            unsigned* childId = (unsigned*)(currentPosition + sizeof(unsigned));
            vis.addChildRelation(pageId, i + 1, *childId);
            Node child(*childId, context);
            child.visualize(vis);
        }

        nodeDes += std::move(keyDes) + std::move(keyVal) + " | " + std::move(ptrDes) + std::move(ptrVal) + " | ";
        currentPosition += sizeof(unsigned) + context.keyLen;
    }

    nodeDes += "\"];";
    vis.addNode(nodeDes);
    //node0 [shape=record, label="<count> 2 | <isLeaf> false | <key0> NL | <key1> US | <key2> | <key3> | <ptr0> * | <ptr1> * | <ptr2> * | <ptr3> | <ptr4>"];
}

void InnerNode::redirectNext(unsigned newNeighbour, bool lastOneDeleted)
{
    char* position = (char*)page.getData() + sizeof(NodeHeader) + header.entryCount * (sizeof(unsigned) + context.keyLen);
    unsigned childId = *(unsigned*)position;
    Node child(childId, context);
    child.redirectNext(newNeighbour, lastOneDeleted);
}

/**
 * Gibt die maximale Anzahl an Einträgen in dem Knoten zurück.
 */
unsigned InnerNode::getMaxEntryCount()
{
	return (pageSize - sizeof(NodeHeader) - sizeof(unsigned)) / (context.keyLen + sizeof(unsigned));
}
